package com.wc.alorithm_blue_bridge._排序.Q1265;

import java.util.Scanner;

/**
 * @Author congge
 * @Date 2023/10/28 10:59
 * @description 排序
 * https://www.lanqiao.cn/problems/1265/learning/?page=1&first_category_id=1&sort=students_count&second_category_id=8
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];

        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
        Main main = new Main();
        main.quickSort(array);
        StringBuffer ans = new StringBuffer();
        ans.append(array[0]);

        for (int i = 1; i < array.length; i++) {
            ans.append(' ');
            ans.append(array[i]);
        }
        ans.append('\n');
        ans.append(array[array.length - 1]);
        for (int i = array.length - 2; i >= 0; i--) {
            ans.append(' ');
            ans.append(array[i]);
        }
        System.out.println(ans);
    }

    /**
     * 快速排序
     *
     * @param array 待排序数组
     */
    public void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    private void quickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }

        int mid = left;
        int i = left + 1;
        int j = right;

        while (true) {
            while (i < right && array[i] < array[mid]) i++;
            while (j > left && array[j] > array[mid]) j--;

            if (i >= j) {
                break;
            }
            swap(array, i, j);
            i++;
            j--;
        }
        swap(array, j, mid);
        quickSort(array, left, j - 1);
        quickSort(array, j + 1, right);
    }

    /**
     * 交换 i j 位置
     * @param array 待交换数组
     * @param i 待交换位置1
     * @param j 待交换位置2
     */
    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}
